package hwThree4;

import java.util.LinkedList;
import java.util.Queue;

public class SequentialSearchST<Key, Value> {
    private Node first; // 链表的首结点


    private class Node {
        Key key;
        Value value;
        Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public Iterable<Key> keys() {
        Queue<Key> queue = new LinkedList<>();
        for (Node x = first; x != null; x = x.next) {
            queue.add(x.key); // 将每个键加入队列
        }
        return queue;
    }
    // 查找键值对，如果存在则返回值，否则返回 null
    public Value get(Key key) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) { // 键匹配
                return x.value;
            }
        }
        return null; // 未找到
    }

    // 插入或更新键值对
    public void put(Key key, Value value) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) { // 如果键已存在，更新值
                x.value = value;
                return;
            }
        }
        // 如果键不存在，头插法插入新键值对
        first = new Node(key, value, first);
    }

    // 删除键值对
    public void delete(Key key) {
        first = delete(first, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        if (key.equals(x.key)) return x.next; // 删除当前结点
        x.next = delete(x.next, key); // 递归删除
        return x;
    }
}
